import collections
class Solution(object):
    def longestStrChain(self, words):
        words.sort(key=lambda x: (len(x), x))
        max_val = 0
        now = collections.defaultdict(int)
        next_dict = collections.defaultdict(int)
        now_length = words[0]
        index = 0
        n = len(words)
        while index < n:
            m = len(words[index])
            max_len = 1
            if m == now_length:
                for i in range(m):
                    max_len = max(max_len, now[words[index][:i] + words[index][i + 1:]] + 1)
                next_dict[words[index]] = max_len
                max_val = max(max_val, max_len)
                index += 1
            else:
                now = next_dict
                next_dict = collections.defaultdict(int)
                now_length = m
        return max_val

data = Solution()
words = ["xbc", "pcxbcf", "xb", "cxbc", "pcxbc"]
print(data.longestStrChain(words))
